package leetcode;

import util.Tree;
import util.TreeNode;

import java.util.*;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0501.java
 * @Author : WangRuoyu
 * @Date 2023/11/11 22:49
 */


public class Q0501 {
    private int maxCount = 0;
    final int K = 100000;
    int[] cnts = new int[100010 + K];

    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        cnts[node.val + K]++;
        maxCount = Math.max(maxCount, cnts[node.val + K]);
        inorder(node.right);
    }

    public int[] findMode(TreeNode root) {
        inorder(root);
        ArrayList<Integer> tmp = new ArrayList<>();

        for (int i = 0; i < cnts.length; i++) {
            if (cnts[i] == maxCount) tmp.add(i - K);
        }

        int[] res = new int[tmp.size()];
        for (int i = 0; i < tmp.size(); i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        Q0501 sl = new Q0501();
        int[] pre = {1, 2};
        int[] in = {1, 2};
        TreeNode root = Tree.createTreeByPreorderAndInorder(pre, in);
        System.out.println(Arrays.toString(sl.findMode(root)));
    }
}